package com.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * 895. 最大频率栈
 * <p>
 * 设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
 * <p>
 * 实现 FreqStack 类:
 * <p>
 * FreqStack() 构造一个空的堆栈。
 * void push(int val) 将一个整数 val 压入栈顶。
 * int pop() 删除并返回堆栈中出现频率最高的元素。
 * 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。
 */
public class LeetCode895 {


    class FreqStack {

        private Map<Integer, Integer> freq;  // 键是push进来的元素，值是元素的属相。
        private Map<Integer, Deque<Integer>> group; // 键是频率，值是相同频率的元素的队列，后push进入的元素会放在后面
        private int maxFreq;

        public FreqStack() {
            freq = new HashMap<>();
            group = new HashMap<>();
            maxFreq = 0;
        }

        public void push(int val) {
            freq.put(val, freq.getOrDefault(val, 0) + 1);
            int valCount = freq.get(val);
            group.putIfAbsent(valCount, new ArrayDeque<>()); // 如果不存在这个频率，才会放进去
            group.get(valCount).push(val);
            maxFreq = Math.max(maxFreq, valCount);
        }

        public int pop() {
            int peekVal = group.get(maxFreq).peek();
            freq.put(peekVal, freq.get(peekVal) - 1);
            group.get(maxFreq).pop();
            // 频率对应的队列已经是空了，频率就要降1，降1之后的频率是一定存在的，因为就是一个一个增加起来的
            if (group.get(maxFreq).isEmpty()) {
                maxFreq--;
            }
            return peekVal;
        }
    }

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack obj = new FreqStack();
 * obj.push(val);
 * int param_2 = obj.pop();
 */

}
